The Fibonacci Sequence¶

$F(1) = 0$

$F(2) = 1$

$F(N) = F(N-1) + F(N-2)\;\;\;\;\;\ $ (for $N > 2$)

The Fibonacci Spiral¶

  • An approximation of the golden spiral created by drawing circular arcs connecting the opposite corners of squares in the Fibonacci tiling
No description has been provided for this image

We can see this in the sunflower, for example:¶

image.png

image.png

image.png

In [ ]:
def fib(n: int) -> int:
        if n == 1:
            return(1)
        elif n == 0:
            return(0)
        else:
            return(fib(n-1)+fib(n-2))

fib(6)

image.png

https://www.mathsisfun.com/games/towerofhanoi.html

  • Also called the Tower of Brahma

  • The Towers of Hanoi actually have very little to do with the city of Hanoi in present day Vietnam.

  • The earliest recorded reference is from Édouard Lucas (in Récréations Mathématiques, Vol. 3, pp. 55–59, Gauthier-Villars, Paris, 1893)..

    • ..who reports that there is in the temple of Kashi Vishwanath in Varanasi, Uttar Pradesh, India, a set of 64 gold disks on 3 diamond needles called the Tower of Brahma which monks have been trying to solve since the beginning of time.

Home work! :-P¶

  • Write a recursive programme to solve the Tower of Brahma.

  • Write an iterative programme to solve the Tower of Brahma.

Tower of Brahma - 1 Disc¶

image-3.png

Solution

  1. tbrahma(1,s,i,d)
    • Move Disc from Source to Destination

Tower of Brahma - 2 Discs¶

image-2.png

Solution

  1. Move Disc 1 from Source to Intermediate
  2. Move Disc 2 from Source to Destination
  3. Move Disc 1 from Intermediate to Destination

Tower of Brahma - 2 Discs¶

image-2.png

Solution

  1. Move Disc 1 from Source to Intermediate
  2. Move Disc 2 from Source to Destination
  3. Move Disc 1 from Intermediate to Destination

Write this in terms of the base case (1 Disc)

Tower of Brahma - 2 Discs¶

image-2.png

Write this in terms of the base case (1 Disc)

  1. Call Disc 1 solution for the first disc with Intermediate and Destination interchanged
    • tbrahma(1,s,d,i)
  2. Call Disc 1 solution for the second disc
    • tbrahma(2,s,i,d)
  3. Call Disc 1 solution for the first disc
    • tbrahma(1,i,s,d)

Tower of Brahma¶

image.png

Tower of Brahma¶

image.png

Solution

  1. Move 2 discs from Source to Intermediate
  2. Move Disc 3 from Source to Destination
  3. Move 2 discs from Intermediate to Destination

Why recursion?¶

  • Recursive thinking is important in programming

    • It helps break down big problems into smaller ones
    • Let's the machine do all the work! :-)
  • Sometimes, it is easier to understand the recursive solution to a problem compared to the iterative one.

  • At times, the recursive implementation may not be as efficient as the iterative one.

In [ ]:
def ifact(n):
    assert n >= 0 and int(n) == n, 'positive integers only!'
    ans = 1
    for i in range(n):
        ans = ans * (i+1)
    return(ans)
In [ ]:
def rfact(n):
    assert n >= 0 and int(n) == n, 'positive integers only!'
    if n == 0 or n == 1:
        return 1
    return(n * rfact(n-1))
In [ ]:
%timeit ifact(2500)
%timeit rfact(2500)
In [ ]:
# compute y = $x^n$ using iteration

def iexp(x,n):
    assert n >= 0 and int(n) == n, 'bad input'
    y = 1 
    if n == 0:
        return 1
    for i in range(n):
        #print(i+1)
        y = y*x
    return(y)
    
In [ ]:
# compute y = $x^n$ using recursion

def r2exp(x,n):
    assert n >= 0 and int(n) == n, 'n must be a positive integer'
    if n == 0:
        return 1
    #print(x,n)
    result = r2exp(x*x,n//2)
    if n % 2 == 0:
        return(result)
    else:
        return(x*result)
In [ ]:
# compute y = $x^n$ using recursion

def r3exp(x,n):
    assert n >= 0 and int(n) == n, 'n must be a positive integer'
    if n == 0:
        return 1
    if n == 1:
        return (x)
    if n == 2:
        return(x*x)
    #print(x,n)
    result = r3exp(x*x*x,n//3)
    rem = n % 3 
    if rem == 0:
        return(result)
    elif rem == 1:
        return(x*result)
    else:
        return(x*x*result)
In [ ]:
iexp(3,4)
rexp(3,4)